#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
   private:
    ListNode* merge(ListNode* l, ListNode* r) {
        // 左边小，合并到左边
        ListNode* head = l;
        while (l && r) {
            while (l->next && l->next->val < r->val) {
                l = l->next;
            }
            ListNode* tmp = r->next;
            r->next = l->next;
            l->next = r;
            r = tmp;
        }
        return head;
    }

   public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1)
            return l2;
        if (!l2)
            return l1;
        if (l1->val <= l2->val)
            return merge(l1, l2);
        if (l2->val <= l1->val)
            return merge(l2, l1);
        return NULL;
    }
};

int main() {
    cout << "Hello, World!";
    ListNode* tmp = new ListNode(1);
    tmp->next = new ListNode(2);
    tmp->next->next = new ListNode(3);
    tmp->next->next->next = new ListNode(4);
    ListNode* tmp1 = new ListNode(5);
    tmp1->next = new ListNode(6);
    tmp1->next->next = new ListNode(7);
    tmp1->next->next->next = new ListNode(8);
    Solution().mergeTwoLists(tmp1, tmp);
    return 0;
}